The present invention relates generally to a memory controller, and more particularly to a method and apparatus for resolving a deadlock situation via collapsing of writebacks to a memory.
Cache memories are typically used in computer systems to decrease the memory access time of processors thereof. A cache memory is a relatively small, high speed memory in which previously accessed information (program instructions and/or data) are stored within cache lines of the cache memory. A cache memory is typically faster than main memory by a factor of 5 to 10 and typically approaches the speed of its corresponding processor. By keeping the most frequently accessed data items in the high speed cache memories, the average memory access time of the processors will approach the access time of the cache memories.
In computer systems having multiple processors and cache memories, the gain in performance from improved memory access time is offset somewhat by the added complexity of maintaining cache coherency. Cache coherency is the method of ensuring that all of the processors in a computer system, and their associated cache memories, are using the latest data. This coherency problem specifically occurs when data stored in cache memory is modified. There are two approaches for providing processors of the computer system with modified data stored in the cache memory. The first approach utilizes a write-through cache system. In a write through cache system, modified data is written to and through a first cache memory to the main memory, and any corresponding copy of the modified data that may reside in other cache memories of the computer system is invalidated. Therefore, when processors subsequently attempt to read the modified data, the modified data is supplied from main memory for all processors whose associated cache memory contains no valid copy of the data.
The second approach utilizes a writeback cache system. In a writeback cache system, a processor and associated cache memory must first obtain ownership of a memory location before the processor may modify the memory location in its cache memory. In response to the processor and associated cache memory obtaining ownership of the memory location, the other cache memories invalidate any copy of the memory location which they may contain. After obtaining ownership of the memory location, the processor may write modified data to its associated cache memory without immediately writing the modified data to main memory. Therefore, data in a cache memory may be different than corresponding data in main memory. In order to maintain coherency, the modified data is later written back to the main memory in response to various events. For example, a writeback cache may write the data back to main memory when: a) a first processor requests the use of modified data stored in the associated cache memory of a second processor, b) a cache line having modified data needs to be replaced with a different line from main memory, or c) a periodic flush of cache memory is performed in order to prevent accidental data loss.
A deadlock situation may occur in a multi-processor system that includes a memory controller having two ports for receiving memory requests. For example, the memory controller may decide to process a first memory request that is received via a first bus. The first memory request may require data located in a cache memory that is coupled to the memory controller via a second bus. Therefore, the memory controller may need to propagate the first memory request through to the second bus in order to obtain the data for the first memory request. However, before the memory controller is able to propagate the first memory request through to the second bus, another device may have already issued a second memory request on the second bus. The memory controller may decide that in order to process the second memory request, the second memory request needs to be propagated through to the first bus. If the memory controller cannot delay processing of either the first memory request or the second memory request, then a deadlock situation will occur because the first memory request is blocking the completion of the second memory request on the first bus and the second memory request is blocking the completion of the first memory request on the second bus.
What is needed therefore is a method and apparatus which resolves the above deadlock situations in a dual ported memory controller.